package ltd.smallwang;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * @author justd
 * @date 2024-10-05 09:24
 */
public class Leetcode0380 {

  public Leetcode0380() {

  }

  private final List<Integer> data = new ArrayList<>();

  private final Map<Integer, Integer> includeMap = new HashMap<>();

  private final Random random = new Random();

  public boolean insert(int val) {
    if (includeMap.containsKey(val)) {
      return false;
    }
    data.add(val);
    includeMap.put(val, data.size() - 1);
    return true;
  }

  public boolean remove(int val) {
    if (!includeMap.containsKey(val)) {
      return false;
    }
    if (includeMap.get(val) == data.size() - 1) {
      includeMap.remove(val);
      data.removeLast();
      return true;
    }
    Integer lastElement = data.removeLast();
    Integer deleteIndex = includeMap.get(val);
    includeMap.remove(val);
    includeMap.put(lastElement, deleteIndex);
    data.set(deleteIndex, lastElement);
    return true;
  }

  public int getRandom() {
    int index = (int) (random.nextDouble() * data.size());
    return data.get(index);
  }
}
